/**
 * 
 */
package leetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class FindKClosestElements {
    public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    	int pos=Collections.binarySearch(arr, x);
    	Deque<Integer> res=new ArrayDeque<>();
    	if(pos<0){
    		pos=-pos-1;
    		if(pos-1>=0&&pos<arr.size()&&(x-arr.get(pos-1)<=arr.get(pos)-x)){
    			pos--;
    		}
    	}
    	res.addLast(arr.get(pos));
    	int left=pos-1;
    	int right=pos+1;
    	int curK=1;
    	while (curK<k) {
			curK++;
    		if(left==-1){
    			res.addLast(arr.get(right++));
    			continue;
    		}
    		if(right==arr.size()){
    			res.addFirst(arr.get(left--));
    			continue;
    		}
    		if(x-arr.get(left)<=arr.get(right)-x){
    			res.addFirst(arr.get(left--));
    		}else {
				res.addLast(arr.get(right++));
			}
		}
    	return new ArrayList<>(res);
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arrrr= {1,2,3,4,5};
		ArrayList<Integer> integers=new ArrayList<>();
		for (int i : arrrr) {
			integers.add(i);
		}
		int k=3;
		int x=4;
		System.out.println(new FindKClosestElements().findClosestElements(integers, k, x));
	}

}
